package data.structure.tree.binary;


/**
 *
 */
public class BinarySearchTree<T extends Comparable> {

    private TreeNode<T> root;

    private int size;

    // 为了简单起见 创建树的时候 必须生成根节点
    public BinarySearchTree(TreeNode<T> root) {
        if (root == null) {
            throw new IllegalArgumentException("根节点不能为空");
        }
        this.root = root;
        this.size = 1;
    }

    public BinarySearchTree(T rootData) {
        if (rootData == null) {
            throw new IllegalArgumentException("根节点不能为空");
        }
        this.root = new TreeNode<>(null, null, rootData);
        this.size = 1;
    }

    // 增加元素
    public boolean addNode(T data) {
        // 是否是空数据
        if (data == null) {
            throw new IllegalArgumentException("新增节点不能为空");
        }
        return doAdd(data, root);
    }

    // 删除元素
    public boolean delNode(T data) {
        // 是否是空数据
        if (data == null) {
            throw new IllegalArgumentException("新增节点不能为空");
        }
        // 查询到需要被删除的节点
        TreeNode node = doSearch(data, root);
        // 节点不存在 不需要删除
        if (node == null) {
            return false;
        }
        // 1.要删除的节点没有子节点，从父节点中删除当前节点
        // 2.要删除的节点只有一个子节点，将父节点与子节点相连
        // 3.要删除的节点有两个子节点  删除并获取右子树的最小节点，成为新的父节点 链接本来的两个子树(获取左子树的最大节点也是一样的)

        return true;
    }


    // 查询元素
    public boolean searchNode(T data) {
        // 是否是空树
        if (size == 0) {
            return false;
        }
        return doSearch(data, root) != null;
    }

    private TreeNode doSearch(T data, TreeNode<T> root) {
        if (root == null) {
            return null;
        }
        int compare = data.compareTo(root.getData());
        if (compare == 0) {
            return root;
        }
        if (compare < 0) {
            return doSearch(data, root.getLeft());
        }
        return doSearch(data, root.getRight());
    }

    private boolean doAdd(T data, TreeNode<T> root) {
        if (root == null) {
            return false;
        }
        int compare = data.compareTo(root.getData());
        if (compare == 0) {
            // 数据已存在
            return false;
        }

        if (compare < 0) {
            if (root.getLeft() == null) {
                // 数据小于当前节点，且当前节点的左子节点为空
                root.setLeft(new TreeNode<>(data));
                return true;
            }
            // 递归当前节点的左子节点
            return doAdd(data, root.getLeft());
        }

        if (root.getRight() == null) {
            // 数据大于当前节点，且当前节点的右子节点为空
            root.setRight(new TreeNode<>(data));
            return true;
        }
        // 递归当前节点的右子节点
        return doAdd(data, root.getRight());
    }

//    private boolean doSearch(T data, TreeNode<T> root) {
//        if (root == null) {
//            return false;
//        }
//        return compare(data, root.getData(), t -> doSearch(t, root.getLeft()), t -> doSearch(t, root.getRight()), true);
//    }
//
//    private <V> V compare(T d1, T d2, Function<? super T, ? extends V> f1, Function<? super T , ? extends V> f2, V equal) {
//        if (d1 == null || d2 == null) {
//            throw new IllegalArgumentException("d1&d2 can not be null");
//        }
//        int compare = d1.compareTo(d2);
//        if (compare == 0) {
//            return equal;
//        }
//        if (compare < 0) {
//            return f1.apply(d1);
//        }
//        return f2.apply(d1);
//    }


}
